#include "find.h"
#define DATA_COUNT 1000000
#define COUNT 100
wanghao::Find f;

//全局函数指针数组
int (wanghao::Find::*ptr[])(int*,int,int) = {nullptr,
                    &wanghao::Find::SequentialSearch,
                    &wanghao::Find::BinarySearch,
                    &wanghao::Find::BinarySearch};
enum
{
    SEQUENTIALSEARCH = 1,
    SEQUENCETABLEBINARYSEARCH,
    UNORDERENLISTBINARYSEARCH,
    PERFORMANCECOMPARISON,
    EXIT
};
void ShowMenu()
{
    
    cout << "1.建立顺序表,调用顺序查找" << endl;
    cout << "2.建立顺序表,调用折半查找" << endl;
    cout << "3.建立无序表,快排后折半查找" << endl;
    cout << "4.查找算法性能度对比" << endl;
    cout << "5.退出" << endl;
}
void DispLay()
{
    cout << "------------" << endl;
    cout << "   0.退出   " << endl;
    cout << "   1.查找   " << endl;
    cout << "------------" << endl;
}
void SequentialSearch()
{
    cout << "-----创建" << COUNT << "个随机数,实现顺序查找-----" << endl;
    int* arr = new int[COUNT];
    int index = 0;
    random_device rd;  // 获取随机数种子
    mt19937 gen(rd()); // 以 rd() 初始化 Mersenne Twister 引擎
    uniform_int_distribution<> distrib(10, 1000); // 定义分布范围 [10, 100]
    for (int n = 0; n < COUNT; ++n)
    {
        arr[index++] = distrib(gen);
        cout << arr[n] << " ";
    }
    cout << endl;
    index = 0;
    do
    {
        DispLay();
        cout << "请输入选项:>";
        cin >> index;
        if(index == 1)
        {
            int k = 0;
            cout << "请输入要查找的值>";
            cin >> k;
            int find = (f.*ptr[SEQUENTIALSEARCH])(arr,COUNT,k);
            if(find != -1) cout << "找到了,下标是:" << find << endl;
            else cout << "没找到" << endl;
        }
        else if(index == 0) cout << "退出" << endl;
        else cout << "输入错误,重新输入" << endl;
    }while(index);
    delete[] arr;
}

void BinarySearch()
{
    cout << "-----创建" << COUNT << "个有序数,实现折半查找-----" << endl;
    int* arr = new int[COUNT];
    int index = 0;
    int value = 0;
    random_device rd;  // 获取随机数种子
    mt19937 gen(rd()); // 以 rd() 初始化 Mersenne Twister 引擎
    uniform_int_distribution<> distrib(10, 1000);
    value = distrib(gen);
    for (int n = value; n < COUNT + value;++n)
    {
        arr[index++] = n;
        cout << *(arr + n - value) << " ";
    }
    cout << endl;
    index = 0;
    do
    {
        DispLay();
        cout << "请输入选项:>";
        cin >> index;
        if(index == 1)
        {
            int k = 0;
            cout << "请输入要查找的值>";
            cin >> k;
            int find = (f.*ptr[SEQUENTIALSEARCH])(arr,COUNT,k);
            if(find != -1) cout << "找到了,下标是:" << find << endl;
            else cout << "没找到" << endl;
        }
        else if(index == 0) cout << "退出" << endl;
        else cout << "输入错误,重新输入" << endl;
    }while(index);
    delete[] arr;
}
void SortAndSearchByHalving()
{
    cout << "-----创建" << COUNT << "个随机数,经过快排实现折半查找-----" << endl;
    int* arr = new int[COUNT];
    int index = 0;
    int value = 0;
    random_device rd;  // 获取随机数种子
    mt19937 gen(rd()); // 以 rd() 初始化 Mersenne Twister 引擎
    uniform_int_distribution<> distrib(10, 1000);
    for (int n = 0; n < COUNT;++n)
    {
        value = distrib(gen);
        arr[index++] = value;
    }
    //快排
    f.QuickSort(arr,COUNT);
    for(int i = 0;i < COUNT;i++)
        cout << *(arr + i) << " ";
    cout << endl;
    index = 0;
    do
    {
        DispLay();
        cout << "请输入选项:>";
        cin >> index;
        if(index == 1)
        {
            int k = 0;
            cout << "请输入要查找的值>";
            cin >> k;
            int find = (f.*ptr[SEQUENTIALSEARCH])(arr,COUNT,k);
            if(find != -1) cout << "找到了,下标是:" << find << endl;
            else cout << "没找到" << endl;
        }
        else if(index == 0) cout << "退出" << endl;
        else cout << "输入错误,重新输入" << endl;
    }while(index);
    delete[] arr;
}
void PerformanceAnalysisOfSearchAlgorithm()
{
    cout << "创建" << DATA_COUNT << "个数据,分别调用顺序查找和排序后的折半查找进行查找,计算出时间" << endl;
    int* arr = new int[DATA_COUNT];
    int index = 0;
    int value = 0;
    int begin1 = 0,end1 = 0;
    int begin2 = 0,end2 = 0;
    //造数据
    random_device rd;  // 获取随机数种子
    mt19937 gen(rd()); // 以 rd() 初始化 Mersenne Twister 引擎
    uniform_int_distribution<> distrib(10, 100000000);
    for (int n = 0; n < DATA_COUNT;++n)
    {
        value = distrib(gen);
        arr[index++] = value;
    }
    int k = distrib(gen);
    begin1 = clock();
    f.SequentialSearch(arr,DATA_COUNT,k);
    end1 = clock();
    begin2 = clock();
    f.QuickSort(arr,DATA_COUNT);
    f.BinarySearch(arr,DATA_COUNT,k);
    end2 = clock();
    cout << "暴力查找算法的时间为" << end1 - begin1 << "ms" << endl;
    cout << "快排后二分查找算法的时间为:" << end2 - begin2 << "ms" << endl;
    delete[] arr;
}
void FindAlgorithm()
{
    ShowMenu();
    int input = 0;
    for(;input != 5;)
    {
        cout << "请输入选项:>";
        cin >> input;
        if(input == SEQUENTIALSEARCH) SequentialSearch();
        else if(input == SEQUENCETABLEBINARYSEARCH) BinarySearch();
        else if(input == UNORDERENLISTBINARYSEARCH) SortAndSearchByHalving();
        else if(input == PERFORMANCECOMPARISON)
            PerformanceAnalysisOfSearchAlgorithm();
        else if(input == EXIT) cout << "退出!!!" << endl;
        else cout << "输入错误,请重新输入" << endl;
        ShowMenu();
    }
}
int main()
{
    FindAlgorithm();
    return 0;
}
